Talk:Busy beaver function/Archive 1
Is \(f_{\omega^\text{CK}_1}(n)\) a well-defined function? How to evaluate \(f_{\omega^\text{CK}_1}(2)\), for example? Ikosarakt1 (talk) 11:52, January 28, 2013 (UTC) :We can't, it's uncomputable xD :I have no idea what the fundamental sequence for \(\omega^\text{CK}_1\) is — probably different functions of \(\omega\) stepping up through different levels of recursion. That is, if a fundamental sequence exists. FB100Z • talk • 20:40, January 30, 2013 (UTC) ::Or maybe \(f_{\omega^\text{CK}_1}\) will have to be defined backwards from \(\Sigma\). I dunno. FB100Z • talk • 21:39, February 1, 2013 (UTC) I found site which conjectures definition of \(f_{\omega^\text{CK}_1}(n)\). If it is really that, \(f_{\omega^\text{CK}_1}(2) = f_{\omega}(2) = 2^2 \times 2 = 8\). Ikosarakt1 (talk) 09:05, February 2, 2013 (UTC) \(\Sigma(5)\) Probably, we soon find out whether \(\Sigma(5) = 4098\) or not. According to this list, only 35 machines remains undecided. Ikosarakt1 (talk) 10:07, February 22, 2013 (UTC) Unfortunately, that list is over a decade old and no one has really made progress since. This doesn't seem to be the sort of problem that interests many mathematicians. (There is one J Harland who mentioned he was working towards solving this, but again that was back in 2009.)Deedlit11 (talk) 15:00, February 28, 2013 (UTC) Mathematicians don't care about us *sob* FB100Z • talk • 07:10, March 5, 2013 (UTC) Grounding Nice explanation, FB100Z. I want more 02:51, March 5, 2013 (UTC) That was my work, read history. Ikosarakt1 (talk) 06:29, March 5, 2013 (UTC) :Aw, you ruined my moment of stolen glory :P FB100Z • talk • 07:04, March 5, 2013 (UTC) :Oops! I didn't notice that. Anyway, thanks for improving the explanation, FB100Z! — I want more 08:22, March 5, 2013 (UTC) I'm going to add oracle Turing machines to the informal explanation, but I haven't found a definition that makes sense and is reasonably concrete. Anyone wanna help? FB100Z • talk • 18:47, March 5, 2013 (UTC) I believe that oracle Turing machine looks like that: we have two tapes, two rulesets and oracle box: normal and oracle. Then oracle box can take arbitrary Turing machine program (which is prescribed in the oracle ruleset), and test whether it halts or not. If not, then write nothing at the current oracle cell blank or write 1 otherwise, move into the direction according to the oracle ruleset. Ikosarakt1 (talk) 21:06, March 5, 2013 (UTC) Nice construction, Ikosarakt. I had conceived of an oracle as something like the following: it's a Turing machine with one tape and one ruleset, however, there is a special oracle state (we'll call it state O). When in the oracle state, the Turing machine does not check whether the currect cell is 1 or 0, but rather counts the number of consecutive 1's starting from the currect cell and moving to the left. If that number is n, the oracle will instantly check whether the nth Turing machine halts or doesn't halt. If it halts, one set of instructions (go to state, write either 0 or 1, move either right or left) is executed; if it doesn't halt, another set of instructions is executed. I think this is powerful enough to define an oracle machine, although I haven't proven it. Deedlit11 (talk) 20:44, March 6, 2013 (UTC) Number of consecutive 1's can be very large and larger than the number of TM's with some number of states. For example, there exists 20736 TM's with 2 states, but if there will be, say, 30000 consecutive 1's, we need to check non-existed TM, thus the function freeze. Ikosarakt1 (talk) 22:24, March 6, 2013 (UTC) The oracle in my oracle Turing machine is not limited to 2-state or n-state Turing machines; it can test a Turing machine with any number of states (limited of course by the maximum number of 1's the oracle Turing machine can print out). It's actually important that the oracle can test Turing machines with arbitrarily many states. If your n-state oracle Turing machine can only test Turing machines with n states or less, than it can't evaluate BB(n+1), for example. So it can't evaluate the general function BB(m), much less BB^m(m) and higher functions. So your oracle Turing machine is far less powerful than it needs to be. Remember, we need to be able to evaluate any algorithm where functions Halt(m) and BB(m) are allowed. Deedlit11 (talk) 23:17, March 6, 2013 (UTC) Multi-head TMs Let reconstruct TM such that head moves instead of tape. Then we can add more heads and for each head specify a separate ruleset. Initially all heads occupy one position. Define \(\Sigma(a,b,c)\) to be largest finite number of non-zeros that can be written on the a-state, b-color, c-head Turing machine. Ikosarakt1 (talk ^ 10:52, March 15, 2013 (UTC) :Since a busy beaver uses up a finite amount of space, we can place the machines far apart from each other so they don't interact during their computations. This means that in general \(\Sigma(a, b, c \cdot d) \geq \Sigma(a, b, c) \cdot d\). Also \(S(a, b, c) \geq S(a, b)\). FB100Z • talk • 18:24, March 18, 2013 (UTC) Yes, but under my definition, all heads initially started from the same place. Ikosarakt1 (talk ^ 18:31, March 18, 2013 (UTC) :Oops. I believe the bounds still hold, though. FB100Z • talk • 18:47, March 18, 2013 (UTC) That's an example of 1-state, 2-headed Turing machine that writes 2 ones on the tape and performs 3 steps. Nearest caret indicates the position of 1st head and otherwise. Ruleset for the 1st head: a _ 1 r halt Ruleset for the 2nd head: a _ 1 r halt a 1 1 l a 0000000000 1st head state = a; 2nd head state = a; Steps = 0 ^ ^ 0000100000 1st head state = a; 2nd head state = halt; Steps = 1 ^ 0000100000 1st head state = a; 2nd head state = halt; Steps = 2 ^ 0000100000 1st head state = halt; 2nd head state = halt; Steps = 3 Therefore, \(\Sigma(1,2,2) \geq 2\) and \(S(1,2,2) \geq 3\). Ikosarakt1 (talk ^ 18:57, March 18, 2013 (UTC) BB(50) I know there is proof that the BB(64) greater than the Graham's number. can we prove that, for example BB (50) greater than the Graham's number? Konkhra (talk) 08:02, March 26, 2013 (UTC) We can't prove it if it isn't true. Only obvious way to do it is to find explicit 50-state TM which writes more than G symbols. If there is no such machine, I'm pretty sure we win't be able to prove it. LittlePeng9 (talk) 14:45, March 26, 2013 (UTC) I think the best way to find bounds for values of TMs is to develop a micro-language that can compile into Turing machines. Maybe find an isomorphism between, say, Brainfuck and TMs? FB100Z • talk • 17:34, March 26, 2013 (UTC) :That may make it easier to write programs that right large numbers, at the expense of parsimony; running a program through an interpreter won't get us Turing machines as small as if we programmed Turing machines natively. The question is if it is really easier to program larger numbers in Brainfuck than in Turing machines. How short a Brainfuck program can we write that outputs a number larger than Graham's number? Deedlit11 (talk) 23:31, March 27, 2013 (UTC) Sorry for a silly question, but what is an isomorphism? Ikosarakt1 (talk ^ 10:10, March 27, 2013 (UTC) Here I think we can define it as strong correlation. Compiler of TM in Brainfuck would allow us to see how is BB_F(n) (busy beaver function for Brainfuck) related to BB(n) LittlePeng9 (talk) 12:48, March 27, 2013 (UTC) "Don't move" variation How about variation of \(\Sigma(n)\) such that TMs also allowed to don't move (just change state) in their rules? Ikosarakt1 (talk ^ 11:39, April 2, 2013 (UTC) No improvement. Consider machine which, when entering square with symbol x in state s, doesn't move for a while. When it finally leaves, it moves, say, to the right, leaves x' on tape and transites to state s'. Same effect would be achived with single transition s,x->x',s',r. So it can be trivially emualted without increasing number of states. It does affect S(n), however, but not significantly. LittlePeng9 (talk) 11:55, April 2, 2013 (UTC) So there exists constant c such that \(\Sigma_{\text{don't move allowed}}(n) = \Sigma(n+c)\). Good, what is this constant? Ikosarakt1 (talk ^ 12:19, April 2, 2013 (UTC) While you ask for Sigma function, c=0. For max shift function, for suffisciently large n, \(S_{\text{don't move allowed}}(n) Ikosarakt1 (talk ^ 10:12, April 6, 2013 (UTC) For multidimensional TMs: Then \(f(n) = \Sigma(c_1,c_2,c_3,n)\) will indeed be eventually constant, for the reasons I explained above. For multihead TMs: Ah, so each head gets its own set of instructions? Interesting. Do you cycle through the instruction sets, applying the rule for the first head, then the rule for the second head, etc.? It appears that this is somewhat weaker than having a single instruction set that reads all inputs, but I wouldn't be surprised if you still got Turing completeness for (c_1, c_2, n). I'm not sure though. Deedlit11 (talk) 03:04, April 8, 2013 (UTC) Yes, I meant that construction. Ikosarakt1 (talk ^ 11:31, April 10, 2013 (UTC) Number theory Is \(\Sigma(5)\) even or odd? What is the last digit of \(\Sigma(7)\)? Will we ever know? FB100Z • talk • 20:04, April 14, 2013 (UTC) To determine numerical properties of \(\Sigma(n)\), we should know TM that computes it. As far as we don't know it, we can't determite it. By the way, there are relevant topic. Ikosarakt1 (talk ^ 20:25, April 14, 2013 (UTC) It may be that \(\Sigma(5)\) is 4098, and someone may be able to prove it in the not to distant future. I imagine that \(\Sigma(7)\) will never be found, and I don't see how we could ever find the last digit without finding the number itself. Deedlit11 (talk) 00:02, April 17, 2013 (UTC) I hope the quantum computer will help us to find \(\Sigma(7)\). May be in the middle of the 21st century or even earlier.Konkhra (talk) 00:06, April 17, 2013 (UTC) Due to speed and memory of quantum computers will grow exponentially, we can assume that, say, in year 2050 mankind will have computer with \(10^{1000000}\) operations per second. Therefore, it will help for finding not only \(\Sigma(7)\), but much more larger values: \(\Sigma(100)\), \(\Sigma(1000)\), and so on. Although they will not compute the exact values, but they will able at least weed out small TM's, which sufficiently makes analysis easier. Ikosarakt1 (talk ^ 10:01, April 17, 2013 (UTC) Number of BB's Can we determine number of Busy Beavers with n states without knowing the table of each? Ikosarakt1 (talk ^ 17:12, April 16, 2013 (UTC) :I doubt it. You need to find the Busy Beavers to know how many there are. We know the number is divisible by 4 though, since we can switch left and right, and the halting state can be either left or right. Deedlit11 (talk) 20:04, April 16, 2013 (UTC)